Comments:

How to efficiently generate combinatorial structures such as posets, trees, B-trees, graphs, permutations, set partitions, Dyck paths, multisets or necklaces ... ? The Ruskey's book gives answers. It contains many surprising descriptions (and bibliographic references) of constant amortized time (CAT) and loopless algorithms.

 

CAT Algorithms The holy grail of generating combinatorial objects is to find an algorithm that runs in Constant Amortized Time. This means that the amount of computation, after a small amount of preprocessing, is proportional to the number of objects that are listed. We do not count the time to actually output or process the objects; we are only concerned with the amount of data structure change that occurs as the objects are being generated.

     Ruskey's book, page 8

 

Loopless algorithm is an imperative algorithm that generates successive combinatorial objects, such as partitions, permutations, and combinations, in constant time and the first object in linear time

     https://en.wikipedia.org/wiki/Loopless_algorithm

Sergey Kirgizov at 2020-06-09 22:01:49
Edited by Sergey Kirgizov at 2020-06-10 21:20:27

Please consider to register or login to comment on the paper.